In a data processing system for storing an instruction group containing at least one branch instruction in the form of an instruction sequence, the processing of the branch instruction is executed in the following manner.
The branch instruction is supplied to a data processor first. Instructions following the branch instruction are then prefetched, and an instruction to be executed subsequently is decided by executing the branch instruction. An example of such a system is disclosed in U.S. Pat. No. 4,200,927. In the disclosed system, however, data processing speed is limited due to the fact that instruction prefetch control is suspended until a result of execution of the branch instruction is clarified.
In order to solve this problem, a system has been proposed in which a result of the execution of a branch instruction is predicted and the instruction prefetch is performed based on the prediction. A data processor can operathe with a minimum processing delay if the prediction is correct. As a prediction system for performing the above, there are several examples conventionally.
A first one of them is a system in which either a "success" side or an "unsuccess" side of predicted branch distination for every branch instruction is predicted.
In another example, a branch destination is predicted on the basis of facts in the past. That is, this system employs the fact that, for a branch instruction, a branch destination has been clarified in a prior result of the same branch instruction and a current branch destination is predicted on the basis of the prior result to improve an accuracy of prediction. A typical example of such a system is disclosed in U.S. Pat. No. 4,477,872.
As another example, there is a system having a number of branch instruction flags for predicting branch destinations corresponding to branch instructions and the flags are referred to in response to occurrences of branch instructions to predict the branch destinations.
In any of these systems, however, the readout and decoding of the branch instruction are required and data processing is delayed by the readout and decoding time even when the prediction is correct.
U.S. Pat. No. 4,604,691 discloses a prediction system for solving the above-mentioned problem. In the latter system, a branch destination address of a branch instruction, which is contained in a block of an instruction cache memory which is a copy of the instruction portion of a main memory, is stored in a memory unit as an address of a block to be fetched subsequent to the former block corresponding to the block of the instruction cache memory. In an instruction prefetch, the memory unit is accessed simultaneously with the accessing of the instruction cache memory to read out the branch destination address, and the address of the instruction to be prefetched is determined by the branch destination address read out. This system is effective to speed up the data processing contrarily to the previously mentioned systems. However, in this system, the prediction is performed by using a block-to-block correspondency of the instruction cache memory. Therefore, when a plurality of branch instructions exist in a block, it is impossible to predict correspondingly to respective branch instructions. Thus, accuracy of prediction in this system is relatively low.
European Patent Application Publication No. 0109655A2 published on May 30, 1984 discloses a prediction system of high accuracy. This system utilizes a branch history table in general. In this system, the address of a branch instruction and a branch destination address are paired and stored in the table. By searching the table with an instruction prefetch address in prefetching the instruction, it is possible to obtain an address of a branch destination to be executed subsequently.
There are many systems of zone management of the main memory. One of them is to manage it by means of segments represented by segment descriptors. Each segment descriptor describes information such as a base address, a boundary and a flag which are necessary for segment management. The base address and the boundary indicate a lower and upper limits of the zone, respectively, and the flag gives a segment access mode.
In the data processing system which utilizes the segments to manage the main memory, the segment descriptor which indicates the size of the segment in picking up an instruction addressed by a branch destination address is unknown until the branch instruction is decoded completely. Therefore, when it is branched to around a boundary area of the segment zone, it may occur to prefetch an instruction even when it is an access to an area outside the segment zone.
Further, in this system, the prefetch of the branch destination instruction is performed prior to the decoding stage of the branch instruction. Therefore, there may be a plurality of instructions from a time at which the branch instruction is prefetched to a time at which the branch instruction is decoded. When an instruction instructing an access mode change for the memory means is contained in a plurality of instructions, the memory means may be accessed in an erroneous access mode.